﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;
//int main()
//{
//	vector<int> dp(1000);
//	dp[0] = 0;
//	dp[1] = 1;
//	for (int i = 2; i < dp.size(); i++)
//	{
//		dp[i] = dp[i - 1] + dp[i - 2];
//	}
//	int n,min=INT_MAX;
//	cin >> n;
//	for (int i = 0; i < dp.size(); i++)
//	{
//		int tmp = abs(dp[i] - n);
//		if (min > tmp) min = tmp;
//	}
//	cout << min << endl;
//	return 0;
//}

//int main()
//{
//	int n;
//	cin >> n;
//	vector<vector<int>> ret(n);
//
//	for (int i = 0; i < n; i++)
//	{
//		vector<int> tmp(i + 1);
//		ret[i] = tmp;
//		for (int j = 0; j <= i; j++)
//		{
//			if (j == 0 || j == i) ret[i][j] = 1;
//			else if (j >= 1 && i >= 1)
//				ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j <= i; j++)
//		{
//			printf("%5d", ret[i][j]);
//		}
//		cout << endl;
//	}
//	return 0;
//}

//int main()
//{
//	vector<string> v;
//	string s;
//	//["XYZE","SFZS","XDEE"],"XYZZED"
//	getline(cin, s);
//	size_t pos = s.find(",");
//	size_t end = s.rfind(",");
//	size_t len = pos - 3;
//	int i = 0;
//	while (pos < end)
//	{
//		string tmp = s.substr(pos - len-1, len);
//		v.push_back(tmp);
//		pos++;
//		pos = s.find(",",pos);
//	}
//	string tmp = s.substr(pos - len - 2, len);
//	v.push_back(tmp);
//	string com = s.substr(end + 2);
//	com.erase(com.size() - 1);
//
//	vector<vector<int>> nums;
//	int row = v.size(), col = v[0].size();
//	for (int i = 0; i < row; i++)
//	{
//		for (int j = 0; j < col; j++)
//		{
//			if (v[i][j] == com[0])
//			{
//
//				return true;
//			}
//		}
//	}
//	return false;
//	return 0;
//}

//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int left = 0, right = 0, n = nums.size();
//        if (n == 1) return 1;
//        while (right < n)
//        {
//            while (right < n && nums[left] == nums[right])
//            {
//                right++;
//            }
//            if (right < n)
//                nums[++left] = nums[right];
//        }
//        return left + 1;
//    }
//};
//int main()
//{
//	vector<int>array;
//	array.push_back(100);
//	array.push_back(300);
//	array.push_back(300);
//	array.push_back(300);
//	array.push_back(300);
//	array.push_back(500);
//	vector<int>::iterator itor;
//	for (itor = array.begin(); itor != array.end(); itor++)
//	{
//		if (*itor == 300)
//		{
//			itor = array.erase(itor);
//		}
//	}
//	for (itor = array.begin(); itor != array.end(); itor++)
//	{
//		cout << *itor << " ";
//	}
//	return 0;
//}
//class Solution {
//public:
//
//    int MoreThanHalfNum_Solution(vector<int>& nums) {
//        int hash[10001] = { 0 };
//        for (int i = 0; i < nums.size(); i++)
//        {
//            hash[nums[i]]++;
//        }
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (hash[i] >= nums.size() / 2)
//                return i;
//        }
//    }
//};

//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param numbers int整型vector
//     * @return int整型
//     */
//    int MoreThanHalfNum_Solution(vector<int>& nums) {
//        // write code here
//        vector<int> hash(10001);
//        int n = nums.size();
//        if (n == 1) return nums[0];
//
//        for (auto x : nums)
//        {
//            hash[x]++;
//        }
//        int i = 0;
//        for (i = 0; i < 10001; i++)
//        {
//            if (hash[i] > n / 2)
//                break;
//        }
//        return i;
//    }
//};

//class Solution {
//public:
//    vector<string> letterCombinations(string digits) {
//        vector<string> combinations;
//        if (digits.empty()) {
//            return combinations;
//        }
//        unordered_map<char, string> phoneMap{
//            {'2', "abc"},
//            {'3', "def"},
//            {'4', "ghi"},
//            {'5', "jkl"},
//            {'6', "mno"},
//            {'7', "pqrs"},
//            {'8', "tuv"},
//            {'9', "wxyz"}
//        };
//        string combination;
//        backtrack(combinations, phoneMap, digits, 0, combination);
//        return combinations;
//    }
//
//    //combinations返回所有组合  phoneMap每个号码对应的多位数字
//    //digits="23"   combination一个组合  
//    void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, 
//        const string& digits, int index, string& combination) {
//        if (index == digits.length()) {
//            combinations.push_back(combination);
//        }
//        else {
//            char digit = digits[index];
//            const string& letters = phoneMap.at(digit);
//            for (const char& letter : letters) {
//                combination.push_back(letter);
//                backtrack(combinations, phoneMap, digits, index + 1, combination);
//                combination.pop_back();
//            }
//        }
//    }
//};
//
//int main()
//{
//    Solution s;
//    s.letterCombinations("23");
//    return 0;
//}